# Асимптотические представления

## Символ O ("О большое") - ограничение сверху

Запись \\(O(f(n))\\) обозначает следующее: существуют положительные константы \\(M\\) и \\(n\_{0}\\), 
такие, что величина \\(x\_{n}\\), представленная в виде \\(O(f(n))\\),
удовлетворяет условию \\(\left|x\_{n}\right| \leq M \left|f(n)\right|\\) для всех целых \\(n \geq n\_0\\). 

### Некоторые свойства "О большого"

- **Формула 1**: \\(f(n) = O(f(n))\\).
- **Формула 2**: \\(c*O(f(n)) = O(f(n))\\), если c - константа.
- **Формула 3**: \\(O(f(n)) + O(f(n)) = O(f(n))\\).
- **Формула 4**: \\(O(O(f(n))) = O(f(n))\\).
- **Формула 5**: \\(O(f(n))O(g(n)) = O(f(n)g(n))\\).
- **Формула 6**: \\(O(f(n)g(n)) = f(n)O(g(n))\\).

## Символ \\(\Omega\\) ("большая омега") - ограничение снизу

Утверждение \\(g(n) = \Omega(f(n))\\) означает, что существуют положительные константы \\(L\\) и \\(n\_{0}\\), 
такие, что \\(\left|g(n)\right| \geq L \left|f(n)\right|\\) для всех целых \\(n \geq n\_0\\).

## Символ \\(\Theta\\) ("большая тета") - ограничение сверху и снизу

\\(g(n) = \Theta(f(n)) \Leftrightarrow g(n) = O(f(n))\\) и \\(g(n) = \Omega(f(n)) \\)

---

**Ссылки:**

- [The Art of Computer Programming - Donald E. Knuth, section 1.2.11.1](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)
